package algorithm.union;

/**
 * @author bingo
 * @Date 2018/3/10
 */
public class UnionFind2 {


    private int[] parent;

    private int count;

    public UnionFind2(int n) {
     parent = new int[n];
     count = n;
     for(int i=0;i<n;i++){
         parent[i] = i;
         }
     }

    /**
     *          0 1 2 3 4 5 6 7 8 9
     *          ------------------------
     * parent： 0 1 2 3 4 5 6 7 8 9
     *
     *          0 1 2 3 4 5 6 7 8 9
     *          ------------------------
     * parent： 0 0 1 3 4 5 6 7 8 9
     *
     * */

    /**找到根节点*/
    public int find(int p){
        assert p >=0 && p<count;

        while(parent[p]!=p){
             p=parent[p];
            }

            return p;
    }

    /**判断他们的根是否相连*/
    public boolean isConnected(int p,int q){

        return  find(p)==find(q);

    }

    public void unionElements(int p,int q){

        int pRoot = find(p);
        int qRoot = find(q);
        if(pRoot==qRoot){
             return;
         }
         parent[pRoot] = qRoot;


   }

    public static void main(String[] args) {
        UnionFind2 unionFind2 = new UnionFind2(10);
        for(int i=0;i<10;i++){
            System.out.print(unionFind2.parent[i]+",");
        }
        System.out.println();
        unionFind2.unionElements(1,0);
        unionFind2.unionElements(2,1);
       /* unionFind2.unionElements(2,3);
        unionFind2.unionElements(3,4);
        unionFind2.unionElements(4,4);
        unionFind2.unionElements(5,5);
        unionFind2.unionElements(7,8);
        unionFind2.unionElements(8,9);*/
        for(int i=0;i<10;i++){
            System.out.print(unionFind2.parent[i]+",");
        }
    }



}
